class Solution {
public:
    const int MOD = 1000000007;
    int numTilings(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 5;
        long long p3 = 1, p2 = 2, p1 = 5;
        long long ans = 0;
        for (int i = 4; i <= n; i++) {
            ans = ((2 * p1) % MOD + p3) % MOD;
            p3 = p2;
            p2 = p1;
            p1 = ans;
        }
        return ans;
    }
};